package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/6/11 20:30
 */
public class ReverseList_206 {

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            // 需要用一个临时结点来存储前驱结点
            ListNode temp = head.next;
            // 将当前结点的下一指针指向下一个结点
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }


    // 从尾到头执行的反转操作
    public ListNode reverseListTraverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

    static class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode node = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return node;
        }

        public ListNode reverseListIterable(ListNode head) {
            ListNode pre = null;
            while (head != null) {
                ListNode temp = head.next;
                head.next = pre;
                pre = head;
                head = temp;
            }
            return pre;
        }

    }

}
